package com.algorithms.techniques;

import java.util.Arrays;
import java.util.Random;

public class RandomizedSelect 
{
	int[] arrayToFindNum=null;
	public RandomizedSelect(int[] arrayToFindNum1)
	{
		arrayToFindNum=Arrays.copyOf(arrayToFindNum1, arrayToFindNum1.length);
		
	}
	
	public int randomSelect(int start,int end,int position)
	{
		if(start==end)
			{System.out.println(arrayToFindNum[start]);
			return arrayToFindNum[start];
			}
		else
		{
			int randomPartition= randomPartition(start,end);
			if(randomPartition==position)
			{
				System.out.println(arrayToFindNum[randomPartition]);
				return arrayToFindNum[randomPartition];
			}
			else
			{
				if(randomPartition>position)
					randomSelect(start,randomPartition-1,position);
				else
					randomSelect(randomPartition+1,end,position-start);
				return -1;
			}
		}
	}
	
	private int randomPartition(int p,int r)
	{
		Random rand = new Random();	
		int num=p+rand.nextInt(r-p);
		//System.out.println("Random="+num);
		swap(num,r);
		return partition(p,r);
	}
	private int partition(int p,int r)
	{
		int pivot =arrayToFindNum[r];
		int i=p-1;
		for(int j=p;j<r ;j++)
		{
			if(arrayToFindNum[j] <pivot)
			{
				i=i+1;
				swap(i,j);
			}
		}
		swap(i+1,r);
		return i+1;
		
	}
	
	private void swap(int pos1,int pos2)
	{
		int temp=arrayToFindNum[pos1];
		arrayToFindNum[pos1]=arrayToFindNum[pos2];
		arrayToFindNum[pos2]=temp;
	}

}
